﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
namespace PrimaryAlgorithm.RemoveNthFromEnd
{
    class MainProject
    {
        static void Main(string[] args)
        {
            //Console.WriteLine(CountAndSay(9));
            ListNode listNode1 = new ListNode(1);
            //ListNode listNode2 = new ListNode(2);
            //ListNode listNode3 = new ListNode(3);
            //ListNode listNode4 = new ListNode(4);
            //ListNode listNode5 = new ListNode(5);
            //listNode1.next = listNode2;
            //listNode2.next = listNode3;
            //listNode3.next = listNode4;
            //listNode4.next = listNode5;
            RemoveNthFromEnd(listNode1, 1);
            Console.ReadKey();
        }
        public static ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            //if (head.next == null && n==1)
            //{
            //    return null;
            //}
            RemoveNth(head,n,null);
            return head;
        }
        //测试
        public static void RemoveNth(ListNode node, int n, ListNode lastNode)
        {
            //结论：引用类型传递形参时候，是生成新的变量，然后在赋值地址
            node =null;
        }

        public static int RemoveNth1(ListNode node, int n,ListNode lastNode)
        {
            //递归
            if (node==null)
            {
                return 0;
            }

            int count = RemoveNth1(node.next, n, node);
            count++;
            if (count==n)
            {
                if (node.next == null)
                {
                    if (lastNode == null)
                    {
                        node = null;
                    }
                    else
                    {
                        lastNode.next = null;
                    }
                }
                else
                {
                    if (lastNode==null)
                    {
                        node.val = node.next.val;
                        node.next = node.next.next;
                    }
                    else
                        lastNode.next = node.next;
                    //node.val = node.next.val;
                }
            }
            return count;
            //return --n;
        }
    }
}
